package dpDemo

import "fmt"

func dpWork() {
	items := []int{0, 1, 2}
	backpack := 4
	weight := map[int]int{0: 1, 1: 3, 2: 4}
	value := map[int]int{0: 15, 1: 20, 2: 30}

	// 初始化dp数组，这里的表示为标号到达i、容量到达j的最大价值
	dp := make([][]int, len(items))
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, backpack+1)
	}
	// 先遍历物品再遍历背包,现在这个01背包问题先遍历背包再遍历物品也是可以的，但是完全背包涉及同一物品数量就不能倒反。
	for i := 0; i < len(dp); i++ {
		for j := 0; j <= backpack; j++ {
			if i == 0 {
				// 初始化的一部分
				if j >= weight[0] {
					dp[i][j] = value[0]
				} else {
					dp[i][j] = 0
				}
			} else {
				if j < weight[i] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
				}
			}
			fmt.Println(dp)
			//fmt.Println(dp[i-1][j], j-weight[i-1], value[i-1], dp[i-1][j-weight[i-1]]+value[i-1])
		}
	}
	fmt.Println(weight, value, dp)
}

func tongyi() {
	items := []int{0, 1, 2}
	backpack := 4
	weight := map[int]int{0: 1, 1: 3, 2: 4}
	value := map[int]int{0: 15, 1: 20, 2: 30}

	// 初始化dp数组，这里的表示为标号到达i、容量到达j的最大价值
	dp := make([][]int, len(items)+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, backpack+1)
	}
	// 先遍历物品再遍历背包
	for i := 1; i < len(dp); i++ {
		for j := 0; j <= backpack; j++ {
			if j < weight[i-1] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]]+value[i-1])
			}
		}
	}
}

// 这题还可以使用滚动数组的方式进行处理，首先进行

func gundon() {
	// 首先初始化，然后进行双重循环
	items := []int{0, 1, 2}
	backpack := 4
	weight := map[int]int{0: 1, 1: 3, 2: 4}
	value := map[int]int{0: 15, 1: 20, 2: 30}

	dp := make([]int, backpack+1)
	dp[0] = 0
	for i := 0; i < len(items); i++ {
		for j := backpack; j >= weight[i]; j-- {
			// 进行反向遍历，这样可以使同一物品不重复
			dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
		}
	}
	fmt.Println(dp)
}
